/*
 * @lc app=leetcode id=282 lang=cpp
 *
 * [282] Expression Add Operators
 */
class Solution {
    
private:
    map<char, std::function<int(int,int)>> method {
        {'-', [](int a, int b) {return a-b;} },
        {'+', [](int a, int b) {return a+b;} },
        {'*', [](int a, int b) {return a*b;} }
    };
public:
    vector<string> addOperators(string num, int target) {
        int len = num.size();
        vector<string> result;
        map<string, int> m = dowork(num, 0, len-1);
        for (auto it : m) {
            if (it.second == target && it.first != num) {
                result.push_back(it.first);
            }
        }
        return result;
    }

    map<string, int> dowork(const string& input, int st, int ed) {
        if (st == ed) {
            auto s = input.substr(st, 1); 
            return {{s, stoi(s)}};
        }

        map<string, int> m;
        for (int i=st; i<ed; i++) {
            auto m1 = dowork(input, st, i);
            auto m2 = dowork(input, i+1, ed);
            for (auto it1 : m1) {
                for (auto it2 : m2) {
                    for (auto op : method) {
                        if ((it1.first.size() > 1 && it1.first[0] == '0') || 
                                (it2.first.size() > 1 && it2.first[0] == '0')) 
                            continue;
                        auto expression = it1.first+op.first+it2.first;
                        auto ret = op.second(it1.second, it2.second);
                        m.insert({expression, ret});
                    }
                }
            }
        }
        auto sv = input.substr(st,ed-st+1);
        if (stol(sv) < INT_MAX) {
            m.insert({sv, stoi(sv)});
        }
        return m;
    }

};

